import java.util.*;

/**
 * https://leetcode.cn/problems/network-delay-time/description/
 */

public class 网络延迟时间 {

    public int networkDelayTime(int[][] times, int n, int k) {
        // 动态建图
        ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
        for(int i = 0;i <= n;i++) {
            graph.add(new ArrayList<>());
        }
        // 0 是出发点, 1 是到达点, 2 是距离
        for(int[] edge : times) {
            graph.get(edge[0]).add(new int[]{edge[1],edge[2]});
        }
        // 构建路线(多1一个位置是因为0位置我们不使用)
        int[] distance = new int[n + 1];
        // 开始标记无穷大
        Arrays.fill(distance,Integer.MAX_VALUE);
        // 构造访问的数组, 防止重复访问
        boolean[] vis = new boolean[n + 1];
        // 构造小根堆
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]);
        // 源点标记一下距离为 0, 并添加到小根堆中
        distance[k] = 0;
        heap.add(new int[]{k,0});
        // 当堆中没有元素就退出
        while (!heap.isEmpty()) {
            // 弹出首个点, 值已经在之前更新了, 不需要更新, 我们只需要遍历该点到达的地方
            int u = heap.poll()[0];
            // 访问过直接跳过这个点
            if(vis[u]){
                continue;
            }
            // 没弹出过标记一下
            vis[u] = true;
            // 开始遍历这个点到达的所有点
            for (int[] edge : graph.get(u)) {
                int a = edge[0];// 代表到达点
                int b = edge[1];// 代表距离
                // 更新并添加的前提, 到达点未被弹出, 并且从弹出的出发点到达(到达点)的距离要更小才会进行更新
                if(!vis[a] && distance[u] + b < distance[a]) {
                    distance[a] = distance[u] + b;
                    heap.add(new int[]{a,distance[a]});
                }
            }
        }
        // 返回值一定要找到最大值, 因为我们存储的是到达每个点的最小距离
        int ans = Integer.MIN_VALUE;
        for(int i = 1;i <= n;i++) {
            // 如果发现无穷大, 无法到达所有点
            if(distance[i] == Integer.MAX_VALUE) {
                return -1;
            }
            // 更新最大值
            ans = Math.max(distance[i],ans);
        }
        return ans;
    }

    public static int MAXN = 101;
    public static int MAXM = 6001;
    public static int[] head = new int[MAXN];// 边号 出发点
    public static int[] next = new int[MAXM];// 下一个的边号 边号
    public static int[] to = new int[MAXM];// 到达点 边号
    public static int[] weight = new int[MAXM];// 距离 边号
    public static int cnt = 1;
    public static int networkDelayTime1(int[][] times, int n, int k) {
        // 链式前向星建图
        // 0 是出发点, 1 是到达点, 2 是距离
        for(int[] edge : times) {
            build(edge[0],edge[1],edge[2]);
        }
        // 构建路线(多1一个位置是因为0位置我们不使用)
        int[] distance = new int[n + 1];
        // 开始标记无穷大
        Arrays.fill(distance,Integer.MAX_VALUE);
        // 构造访问的数组, 防止重复访问
        boolean[] vis = new boolean[n + 1];
        // 构造小根堆
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]);
        // 源点标记一下距离为 0, 并添加到小根堆中
        distance[k] = 0;
        heap.add(new int[]{k,0});
        // 当堆中没有元素就退出
        while (!heap.isEmpty()) {
            // 弹出首个点, 值已经在之前更新了, 不需要更新, 我们只需要遍历该点到达的地方
            int u = heap.poll()[0];
            // 访问过直接跳过这个点
            if(vis[u]){
                continue;
            }
            // 没弹出过标记一下
            vis[u] = true;
            // 开始遍历这个点到达的所有点
            // 先从 head 找到该点的第一个边号, 并遍历所有的边号
            for (int i = head[u]; i != 0; i = next[i]) {
                int a = to[i];// 代表到达点
                int b = weight[i];// 代表距离
                // 更新并添加的前提, 到达点未被弹出, 并且从弹出的出发点到达(到达点)的距离要更小才会进行更新
                if(!vis[a] && distance[u] + b < distance[a]) {
                    distance[a] = distance[u] + b;
                    heap.add(new int[]{a,distance[a]});
                }
            }



        }
        // 返回值一定要找到最大值, 因为我们存储的是到达每个点的最小距离
        int ans = Integer.MIN_VALUE;
        for(int i = 1;i <= n;i++) {
            // 如果发现无穷大, 无法到达所有点
            if(distance[i] == Integer.MAX_VALUE) {
                return -1;
            }
            // 更新最大值
            ans = Math.max(distance[i],ans);
        }
        return ans;
    }

    private static void build(int a, int b, int c) {
        // 如果 head[a] 开始存着一条边号, 要把它作为下一条边号
        // 并更新一下 head[a] 的新边号
        next[cnt] = head[a];
        head[a] = cnt;
        // 更新一下这条边对应的点和权值
        to[cnt] = b;
        weight[cnt++] = c;
    }

    public static void main(String[] args) {
        int[][] times = {
                {2, 1, 1},
                {2, 3, 1},
                {3, 4, 1}
        };
        System.out.println(networkDelayTime1(times, 4, 2));
    }
}
